package Math;

public class _812_LargestTriangleArea {
    //brute force,use heron's formula
    public double largestTriangleArea(int[][] points) {
        double maxArea = Double.MIN_EXPONENT;
        for (int i = 0; i < points.length; i++) {
            for(int j=i+1;j<points.length;j++) {
                for(int k=j+1;k<points.length;k++) {
                    double side_1 = Math.sqrt(Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1],2));
                    double side_2 = Math.sqrt(Math.pow(points[i][0] - points[k][0], 2) + Math.pow(points[i][1] - points[k][1],2));
                    double side_3 = Math.sqrt(Math.pow(points[j][0] - points[k][0], 2) + Math.pow(points[j][1] - points[k][1],2));
                    double halfPerimeter = (side_1 + side_2 + side_3)/2;
                    double tempArea = Math.sqrt(halfPerimeter*(halfPerimeter-side_1)*(halfPerimeter-side_2)*(halfPerimeter-side_3));
                    if (tempArea > maxArea) {
                        maxArea = tempArea;
                    }
                }
            }
        }
        return maxArea;
    }
}
